package solutiondemo;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2024-01-21
 * Time: 0:29
 */

/**
 * 描述
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等。
 * 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 * 1. 0<=pushV.length == popV.length <=1000
 * 2. -1000<=pushV[i]<=1000
 * 3. pushV 的所有数字均不相同
 */
public class Solution {
    /**
     * 解法二: 高雅判断，pushV.length == popV.length，只需要判断popV能否遍历完即可
     * @param pushV
     * @param popV
     * @return
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {

        Stack<Integer> stack = new Stack<>();
        int pushIndex = 0;
        int popIndex = 0;

        //当待检测数组遍历完
        while(popIndex < popV.length) {
            //先入栈，直至有第一个匹配
            //判断是否入栈会发生两种情况:
            //1.栈内无元素（初始条件） 2.栈顶元素不匹配
            //确定需要入栈后:
            // 1.pushV内无元素，无法入栈
            //2.pushV内有元素，可以入栈
            while(stack.empty() || stack.peek() != popV[popIndex]) {
                if(pushIndex < pushV.length) {
                    stack.push(pushV[pushIndex]);
                    pushIndex++;
                }else {
                    return false;
                }
            }
            //这时出栈，说明栈顶元素发生匹配
            stack.pop();
            popIndex++;
        }
        return true;
    }

/**
 * 解法一：
  */

//    public boolean IsPopOrder (int[] pushV, int[] popV) {
//
//        Stack<Integer> stack = new Stack<>();
//        int i = 0;  //用来遍历pushV
//        int j = 0;  //用来遍历popV
//
//        //数据没有全部入栈
//        while(i < pushV.length) {
//            //如果栈为空，则入栈
//            if(stack.empty()) {
//                stack.push(pushV[i]);
//                i++;
//            }
//
//            while(!stack.empty()) {
//                if(stack.peek() == popV[j]) {
//                    stack.pop();
//                    j++;
//                }else {
//                   break;
//                }
//            }
//            if(i < pushV.length) {
//                stack.push(pushV[i]);
//                i++;
//            }
//
//
//        }
//
//        //如果遍历完栈后，栈内仍有元素
//        while(!stack.empty()) {
//            if(stack.peek() == popV[j]) {
//                stack.pop();
//                j++;
//            }else {
//                return false;
//            }
//        }
//
//        return true;
//    }
}
